#pragma once

#include <iostream>
#include <vector>
#include "compare.h"

using namespace std;

// imprime um vetor
template<typename T>
void printVector(const vector<T> &v)
{
  int i = 0;
  for (; i < int(v.size()) - 1; i++) {
    cout << v[i] << ", ";
  }

  if (i < v.size()) {
    cout << v[i] << endl;
  }
}

// retorna true se um vetor está ordenado. Usado para confirmar uma ordenação
template<typename T>
bool assertSorted(const std::vector<T> &v, const function<bool(const T&, const T&)> &compare = CompareMax<T>())
{
  if (v.size() < 2) {
    return true;
  }

  int i = 1;

  for (; i < v.size() && (compare(v[i],v[i-1]) || v[i] == v[i-1]); i++);

  return i == v.size();
}

/**
 * @brief gera um vector com n elementos aleatórios do tipo T
 * @param T um tipo de dado
 * @param n o tamanho do array gerado
 */
template<typename T> 
vector<T> generateRandomData(int n);

template<>
vector<int> generateRandomData(int n)
{
  vector<int> r;
  r.reserve(n);

  for (int i = 0; i < n; i++) {
    r.push_back(rand());
  }

  return r;
}

template<>
vector<string> generateRandomData(int n)
{
  vector<string> r;
  for (int i = 0; i < n; i++) {
    string s;
    for (int i = 0; i < 10; i++) {
      s += char(rand() % 26 + 65);
    }
    r.push_back(s);
  }

  return r;
}

template<typename T>
vector<T> generateAscSortedData(int n);

template<typename T>
vector<T> generateDescSortedData(int n);

template<>
vector<int> generateAscSortedData(int n)
{
  vector<int> r;
  r.reserve(n);
  for (int i = 0; i < n; i++) {
    r.push_back(i);
  }
  return r;
}

template<>
vector<int> generateDescSortedData(int n)
{
  vector<int> r;
  r.reserve(n);
  for (int i = n; i > 0; i--) {
    r.push_back(i);
  }
  return r;
}

template<>
vector<string> generateAscSortedData(int n)
{
  vector<string> r;
  r.reserve(n);

  // o primeiro elemento, que será base para os próximos
  string base = "aaaaaaaaaa";

  char min = 'a', max = 'z';

  for (int j = 0; j < n; j++) {
    r.push_back(base);

    int i = base.size() - 1;
    bool carry = true;

    do {
      base[i]++;
    
      if (base[i] > max) {
        base[i] = min;
      } else {
        carry = false;
      }
    
    } while (--i >= 0 && carry);
  }

  return r;
}

// FIXME: é basicamente uma cópia de generateAscSortedData<string>()!
// Tenho que refatorá-los e procurar usar o mesmo código
template<>
vector<string> generateDescSortedData(int n)
{
  vector<string> r;
  r.reserve(n);

  // o primeiro elemento, que será base para os próximos
  string base = "zzzzzzzzzz";

  char min = 'a', max = 'z';

  for (int j = 0; j < n; j++) {
    r.push_back(base);

    int i = base.size() - 1;
    bool carry = true;

    do {
      base[i]--;
    
      if (base[i] < min) {
        base[i] = max;
      } else {
        carry = false;
      }
    
    } while (--i >= 0 && carry);
  }

   
  return r; 
}
